package com.leetcode.array;

import java.util.HashSet;
import java.util.Set;

/**
 * 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 说明：
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 * 示例 2:
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xm0u83/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年07月23日 16:30
 */
class Code136 {
    public static void main(String[] args) {
        int[] nums = {2,2,1};
        int i = singleNumber2(nums);
        System.out.println(i);
    }

    /**
     * 暴力法
     * @author ymy
     * @date 2021/7/23 16:50
     * @param nums
     * @return int
     */
    public static int singleNumber1(int[] nums) {
        for(int i = 0;i<nums.length;){
            boolean flag = true;
            for (int j = i+1; j < nums.length;) {
                if(nums[i] != nums[j]){
                    j++;
                }else {
                    flag = false;
                    int temp = nums[j];
                    nums[j] = nums[i+1];
                    nums[i+1] = temp;
                    i+=2;
                    break;
                }
            }
            if(flag){
                return nums[i];
            }
        }
        return 0;
    }

    /**
     * 使用额外内存 set
     * @author ymy
     * @date 2021/7/23 16:51
     * @param nums
     * @return int
     */
    public static int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }
        return (int)set.toArray()[0];
    }

    /**
     * 位运算解决
     * 这题说的是只有一个数出现了一次，其他数字都出现了2次，让我们求这个只出现一次的数字。这题使用位运算是最容易解决的，关于位运算有下面几个规律
     * 1^1=0;
     * 1^0=1;
     * 0^1=1;
     * 0^0=0;
     * 也就说0和1异或的时候相同的异或结果为0，不同的异或结果为1，根据上面的规律我们得到
     * a^a=0；自己和自己异或等于0
     * a^0=a；任何数字和0异或还等于他自己
     * a^b^c=a^c^b；异或运算具有交换律
     * 有了这3个规律，这题就很容易解了，我们只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字。
     * 作者：数据结构和算法
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xm0u83/?discussion=VumtOv
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @author ymy
     * @date 2021/7/23 16:36
     * @param nums
     * @return int
     */
    public static int singleNumber3(int[] nums) {
        int k = nums[0];
        for(int i = 1;i<nums.length;i++){
            k = k^nums[i];
        }
        return k;
    }
}
